Snarks are a historical class of cubic graphs with peculiar properties motivated by the Four-Color Theorem. In nearly 100 years of search, since its definition by Peter Guthrie Tait in 1880, only five such graphs were identified which motivated Martin Gardner in 1976 to call them snark, a mysterious creature. In 1975, Rufus Isaacs introduced a method known as dot product, which allowed the construction of new snarks from known snarks, and presented the first infinite family of snarks. A new method proposed in 1996 by Martin Kochol allowed to obtaining new snarks from smaller graphs, known as Kochol superposition. However, this method was usually used to obtain snarks with large girth. We applied the Kochol superposition to known snarks: the family of Goldberg snarks (known to be Type 1) and a girth 4 snark recently discovered by Gunnar Brinkmann et al. (known to be Type 2). Surprisingly, when we apply the Kochol superposition to a Type 1 snark with a Type 2 snark, we can obtain new families of snarks of distinct Types: Type 1 and Type 2.

A k-total coloring of a graph G = (V, E) is an assignment of k colors to the elements of G , such that adjacent or incident elements have different colors. Let ∆ be the maximum vertex degree of a graph G , the Total Coloring Conjecture states that every graph G is (∆ + 1), or (∆ + 2)-total colorable. In 1994, McDiarmid and Sánchez-Arroyo proved that the total coloring problem, asking whether a graph G is (∆ + 1)-total colorable, is NP-complete even when G is k -regular, k ≥ 3 and bipartite. In 1988, Chetwynd and Hilton defined conformable vertex coloring in the attempt to characterize the vertex coloring induced by a (∆ + 1)-total coloring. A (∆ + 1)-vertex coloring of a graph G is called conformable if the number of color classes of parity different from that of | V | is at most the deficiency def(G) =∑ v∈V (Δ − dG(v)) of G , where d G ( v) is the degree of a vertex v of V. Recently, it was proved that conformability is polynomial for maximum degree three graphs. However, the general time-complexity of conformability status remains unknown. Not every conformable coloring extends naturally to a (∆ + 1)-total coloring. One might ask when, or what properties a conformable vertex coloring should have to extend to a (∆ + 1)-total coloring. In this paper, we introduce the concept of strong conformable coloring a conformable coloring that extends to a total coloring. A strong conformable coloring is a conformable coloring with two additional properties. We show that each of these two properties is necessary in order to extend a conformable to a total coloring. Furthermore, we prove that a graph G is strong conformable if and only if G has a (∆ + 1)-total coloring. Consequently, we deliver the bad news that strong conformable vertex coloring problem is NP-complete even for bipartite k -regular graphs with k ≥ 3.

A q-total coloring of G is an assignment of q colors to the vertices or edges of G, so that adjacent or incident elements have different colors. The Total Coloring Conjecture (TCC) asserts that a total coloring of a graph G has at least ∆ + 1 and at most ∆ + 2 colors. Rosenfeld has shown that the total chromatic number of a cubic graph is either 4 (Type 1) or 5 (Type 2). We present Type 1 new infinite families of snarks (cubic bridgeless graphs of chromatic index 4) obtained by the Kochol superposition of Goldberg with t-Semiblowup snarks. These results provide evidence of a negative answer for the question proposed by Cavicchioli et al. (2003) about the smallest order of a Type 2 snark of girth at least 5.

A k-total coloring of a graph G is an assignment of k colors to the elements (vertices and edges) of G so that adjacent or incident elements have different colors. The total chromatic number is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. We consider the direct product of complete graphs Km × Kn. It is known that if at least one of the numbers m or n is even, then Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1, except when m = n = 2. We prove that the graph Km × Kn has total chromatic number equal to ∆(Km × Kn) + 1 when both m and n are odd numbers, ensuring in this way that all graphs Km × Kn have total chromatic number equal to ∆ (Km × Kn) + 1, except when m = n = 2.

The search for counterexamples to the Four Color Conjecture originated snarks, a very special class of cubic graphs. In this paper, we consider the equitable total coloring of snarks. A total coloring is equitable if the number of elements colored with each color differs by at most one, and the least integer for which a graph has such a coloring is called its equitable total chromatic number. In 2002, Wang conjectured that the equitable total chromatic number of a graph is at most ∆ + 2, and this was proved for cubic graphs. Therefore, the equitable total chromatic number of a cubic graph is either 4 or 5. We provide evidence to a negative answer to the question proposed in 2016 about the existence of a Type 1 cubic graph with girth greater than 4 and equitable total chromatic number 5, by determining equitable 4-total colorings for every member of three infinite families of snarks with girth 5.

A k-total coloring of a graph G is an assignment of k colors to the vertices and edges (elements) of G so that adjacent or incident elements have different colors. The total chromatic number of G is the smallest integer k for which G has a k-total coloring. The well known Total Coloring Conjecture states that the total chromatic number of a graph is either ∆(G) + 1 or ∆(G) + 2, where ∆(G) is the maximum degree of G. Graphs with χ" (G) = ∆(G) + 1 are known as Type 1, and graphs with χ" (G) = ∆(G) + 2 are known as Type 2. In this work, we investigate the total coloring of circulant graphs. We establish that all members of three infinite families of 4-regular circulant graphs are Type 1, except for one graph which is Type 2. These results contribute to the conjecture proposed by Khennoufa and Togni in 2008, which states that, except for a finite number of Type 2, 4-regular circulant graphs are all Type 1.

A radio network consists of a set of transceiver nodes in space that communicate using broadcast radio. Since communication is done over a shared medium, transmissions are subject to collisions. Different Medium Access Control techniques are used to avoid such collisions and subsequent data loss. In this article, we study Time Division Multiple Access link scheduling in Wireless Multihop Networks. We generalize the packet radio network (PRN)‐coloring model that was used in previous works to obtain the Backbone PRN (BPRN)‐coloring. The BPRN‐coloring captures the fact that typically only a subset of links need to be scheduled, corresponding to the backbone network. We study the BPRN‐coloring and the corresponding BPRN‐chromatic index considering a rooted tree as backbone, motivated by applications in Wireless Sensor Networks. The BPRN‐chromatic index is determined when the whole graph is either a complete graph or a cycle, and we give partial results in the case of a bipartite graph. We show that determining the BPRN‐chromatic index is NP‐hard even when the network graph is bipartite, and the backbone is an oriented tree toward a root vertex. Finally, we model a ring topology as the power of a cycle graph and give an upper bound on the BPRN‐chromatic index. © 2017 Wiley Periodicals, Inc. NETWORKS, Vol. 71(4), 403–411 2018