×

Coloring chip configurations on graphs and digraphs. (English) Zbl 1232.05074

Summary: Let \(D\) be a simple directed graph. Suppose that each edge of \(D\) is assigned with some number of chips. For a vertex \(v\) of \(D\), let \(q^{+}(v)\) and \(q^{ - }(v)\) be the total number of chips lying on the arcs outgoing form \(v\) and incoming to \(v\), respectively. Let \(q(v)=q^{+}(v) - q^{ - }(v)\). We prove that there is always a chip arrangement, with one or two chips per edge, such that \(q(v)\) is a proper coloring of \(D\). We also show that every undirected graph \(G\) can be oriented so that adjacent vertices have different balanced degrees (or even different in-degrees). The arguments are based on peculiar chip shifting operation which provides efficient algorithms for obtaining the desired chip configurations. We also investigate modular versions of these problems. We prove that every \(k\)-colorable digraph has a coloring chip configuration modulo \(k\) or \(k+1\).

MSC:

05C15 Coloring of graphs and hypergraphs
05C20 Directed graphs (digraphs), tournaments
05C85 Graph algorithms (graph-theoretic aspects)
PDFBibTeX XMLCite
Full Text: DOI EuDML

References:

[1] Addario-Berry, L.; Dalal, K.; Reed, B. A., Degree constrained subgraphs, Discrete Appl. Math., 156, 7, 1168-1174 (2008) · Zbl 1147.05055
[2] Bartnicki, T.; Grytczuk, J.; Niwczyk, S., Weight choosability of graphs, J. Graph Theory, 60, 242-256 (2009) · Zbl 1210.05138
[3] Czerwiński, S.; Grytczuk, J.; Żelazny, W., Lucky labelings of graphs, Inform. Process. Lett., 109, 1078-1081 (2009) · Zbl 1197.05125
[4] Hartsfield, N.; Ringel, G., Pearls of Graph Theory (1990), Academic Press · Zbl 0703.05001
[5] M. Kalkowski, Algorithmic approach to irregularity strength, PhD thesis, Adam Mickiewicz University, 2010.; M. Kalkowski, Algorithmic approach to irregularity strength, PhD thesis, Adam Mickiewicz University, 2010.
[6] Kalkowski, M.; Karoński, M.; Pfender, F., Vertex-coloring edge-weightings: towards 1-2-3-conjecture, J. Combin. Theory Ser. B, 91, 151-157 (2004)
[7] Karoński, M.; Łuczak, T.; Thomason, A., Edge weights and vertex colours, J. Combin. Theory Ser. B, 91, 151-157 (2004) · Zbl 1042.05045
[8] Przybyło, J.; Woźniak, M., On a 1, 2 conjecture, Discrete Math. Theor. Comput. Sci., 12, 101-108 (2010) · Zbl 1250.05093
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.