. "1"^^ . "P(1M0545), P(GPP201/10/P337), Z(MSM0021620838)" . . . "2"^^ . . "High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph"@en . . . "High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph" . "[7A1F33851113]" . . . . . "11320" . . . "High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph"@en . "High-Girth Cubic Graphs are Homomorphic to the Clebsch Graph" . "10.1002/jgt.20580" . "000287676100005" . . . . "RIV/00216208:11320/11:10100998" . "0364-9024" . "US - Spojen\u00E9 st\u00E1ty americk\u00E9" . "Graph; Clebsch; Homomorphic; are; Graphs; Cubic; High-Girth"@en . . . "66" . "http://dx.doi.org/10.1002/jgt.20580" . . "DeVos, Matt" . . "Journal of Graph Theory" . "202067" . "3" . "We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4/5 has an edge-cut containing at least of the edges. The existence of such an edge-cut follows immediately from the existence of a 5-edge-coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above-described 5-edge-coloring; hence our theorem may also be viewed as a weak version of Nesetril''s Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C(5))." . "\u0160\u00E1mal, Robert" . . "We give a (computer assisted) proof that the edges of every graph with maximum degree 3 and girth at least 17 may be 5-colored (possibly improperly) so that the complement of each color class is bipartite. Equivalently, every such graph admits a homomorphism to the Clebsch graph (Fig. 1). Hopkins and Staton [J Graph Theory 6(2) (1982), 115-121] and Bondy and Locke [J Graph Theory 10(4) (1986), 477-504] proved that every (sub)cubic graph of girth at least 4/5 has an edge-cut containing at least of the edges. The existence of such an edge-cut follows immediately from the existence of a 5-edge-coloring as described above; so our theorem may be viewed as a coloring extension of their result (under a stronger girth assumption). Every graph which has a homomorphism to a cycle of length five has an above-described 5-edge-coloring; hence our theorem may also be viewed as a weak version of Nesetril''s Pentagon Problem (which asks whether every cubic graph of sufficiently high girth is homomorphic to C(5))."@en . "RIV/00216208:11320/11:10100998!RIV12-GA0-11320___" . . . . "19"^^ .