1. A sharp upper bound for the harmonious total chromatic number of graphs and multigraphsMarién Abreu, John Baptist Gauci, Davide Mattiolo, Giuseppe Mazzuoccolo, Federico Romaniello, Christian Rubio-Montiel, Tommaso Traetta, 2025, izvirni znanstveni članek Opis: A proper total colouring of a graph G is called harmonious if it has the further property that when replacing each unordered pair of incident vertices and edgeswith their colours, then no pair of colours appears twice. The smallest number of colours for it to exist is called the harmonious total chromatic number of G, denoted by h_t(G). Here, we give a general upper bound for h_t(G) in terms of the order n of G. Our two main results are obvious consequences of the computation of the harmonious total chromatic number of the complete graph Kn and of the complete multigraph λK_n, where λ is the number of edges joining each pair of vertices of Kn. In particular, Araujo-Pardo et al. have recently shown that 3/2 n ≤ h_t(K_n)≤ 5/3 n + θ(1). In this paper, we prove that h_t(K_n) = ⌈3/2 n⌉ except for h_t(K₁) = 1 and h_t(K₄) = 7; therefore, h_t(G)≤ ⌈3/2 n⌉, for every graph G on n > 4 vertices. Finally, we extend such a result to the harmonious total chromatic number of the complete multigraph λKn and as a consequence show that h_t(G) ≤ (λ-1)(2⌈n/2⌉-1)+⌈3n/2⌉ for n > 4, where G is a multigraph such that λ is the maximum number of edges between any two vertices.
Ključne besede: total colouring, harmonious colouring, complete graphs, complete multigraphs, Levi graph
Objavljeno v RUP: 03.11.2025; Ogledov: 882; Prenosov: 22
 Celotno besedilo (387,22 KB) |
2. Banff designs: difference methods for coloring incidence graphsMarco Buratti, Francesca Merola, Anamari Nakić, Christian Rubio-Montiel, 2025, izvirni znanstveni članek Opis: We present some results on the harmonious colourings of the Levi graph of a 2-design, focusing on Steiner 2-design. It is easily seen that the harmonious chromatic number of such a Levi graph is at least the number of points of the design: we study and construct Banff designs, that is designs such that this lower bound is attained.
Ključne besede: Harmonious chromatic number, Levi graph, combinatorial design
Objavljeno v RUP: 03.11.2025; Ogledov: 689; Prenosov: 7
Celotno besedilo (426,74 KB) |
3. Splittable and unsplittable graphs and configurationsNino Bašić, Jan Grošelj, Branko Grünbaum, Tomaž Pisanski, 2019, izvirni znanstveni članek Opis: We prove that there exist infinitely many splittable and also infinitely many unsplittable cyclic ▫$(n_3)$▫ configurations. We also present a complete study of trivalent cyclic Haar graphs on at most 60 vertices with respect to splittability. Finally, we show that all cyclic flag-transitive configurations with the exception of the Fano plane and the Möbius-Kantor configuration are splittable.
Ključne besede: configuration of points and lines, unsplittable configuration, unsplittable graph, independent set, Levi graph, Grünbaum graph, splitting type, cyclic Haar graph
Objavljeno v RUP: 03.01.2022; Ogledov: 2801; Prenosov: 29
Celotno besedilo (355,79 KB) |
4. Point-ellipse configurations and related topicsGábor Gévay, Nino Bašić, Jurij Kovič, Tomaž Pisanski, 2021, izvirni znanstveni članek Ključne besede: point-line configuration, conic section, point-ellipse configuration, point-conic configuration, Levi graph, Carnot's theorem
Objavljeno v RUP: 18.10.2021; Ogledov: 4798; Prenosov: 28
 Povezava na celotno besedilo |
