On nice graphs

DOI10.1016/S0012-365X(00)00190-4MaRDI QIDQ5936050zbMATH OpenFDO

Authors Pavol Hell, Alexandr Kostochka, André Raspaud, Éric Sopena

Publication date 8 August 2002

Published in Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/S0012-365X(00)00190-4

zbMATH Keywords

characterizationschromatic numberedge-coloured graphsgraph homomorphismsnice graphsoriented graphsuniversal graphs

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Directed graphs (digraphs), tournaments (05C20)

Review text

A digraph \(D=(V,A)\) is called \(k\)-nice (\(k\)-half-nice) if there exists a positive integer \(k\) such that for every two (not necessarily distinct) vertices \(x,y\) and for every given sequence \(q=(q_1,\dots,q_k)\in\{+,-\}^k,\) there exists a walk in \(D\) starting from \(x\) to \(y\) (starting from \(x\) containing \(y\)) which respects \(q,\) i.e. \(q_i=+\) corresponds to a forward arc and \(q_i=-\) to a backward one. Nice and half-nice multigraphs with \(p\)-coloured edges are defined similarly. The authors obtained several characterizations of the structure of nice and half-nice digraphs, and of nice and half-nice multigraphs. They found minimal numbers of arcs in nice and half-nice digraphs, and minimal numbers of edges in nice and half-nice multigraphs for the given number of vertices. The study of nice graphs is motivated by the problem of determining the oriented chromatic number of some graphs. A graph \(G\) is universal for some class \(C\) of graphs if every graph \(H\in C\) has a homomorphism to \(G.\) Results connecting nice graphs and universal graphs for some classes of planar or outerplanar graphs are included.

Recommendations

• On nice and injective-nice tournaments
• scientific article; zbMATH DE number 549475
• Oriented graph coloring
• Good and semi-strong colorings of oriented planar graphs
• On universal graphs for planar oriented graphs of a given girth

Cited in

(15)

• Homomorphisms from sparse graphs with large girth.
• Nilpotent families of endomorphisms of ( P(V)^+,)
• On fractional version of oriented coloring
• The complexity of signed graph and edge-coloured graph homomorphisms
• On nice and injective-nice tournaments
• \(L(2,1)\)-labelings of some families of oriented planar graphs
• Chromatic number of sparse colored mixed planar graphs
• 2-dipath and oriented L(2, 1)-labelings of some families of oriented planar graphs
• scientific article; zbMATH DE number 5924441 (Why is no real title available?)
• scientific article; zbMATH DE number 5948708 (Why is no real title available?)
• scientific article; zbMATH DE number 4160790 (Why is no real title available?)
• scientific article; zbMATH DE number 139918 (Why is no real title available?)
• On Lict sigraphs
• scientific article; zbMATH DE number 7059509 (Why is no real title available?)
• Complexity of planar signed graph homomorphisms to cycles

This page was built for publication: On nice graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5936050)