Увійти

Готові списки джерел за темами / Properly colored subgraph / Статті в журналах

Щоб переглянути інші типи публікацій з цієї теми, перейдіть за посиланням: Properly colored subgraph.

Статті в журналах з теми "Properly colored subgraph"

Автор: Grafiati

Опубліковано: 25 травня 2024

Оформте джерело за APA, MLA, Chicago, Harvard та іншими стилями

Оберіть тип джерела:

Ознайомтеся з топ-25 статей у журналах для дослідження на тему "Properly colored subgraph".

Біля кожної праці в переліку літератури доступна кнопка «Додати до бібліографії». Скористайтеся нею – і ми автоматично оформимо бібліографічне посилання на обрану працю в потрібному вам стилі цитування: APA, MLA, «Гарвард», «Чикаго», «Ванкувер» тощо.

Також ви можете завантажити повний текст наукової публікації у форматі «.pdf» та прочитати онлайн анотацію до роботи, якщо відповідні параметри наявні в метаданих.

Переглядайте статті в журналах для різних дисциплін та оформлюйте правильно вашу бібліографію.

1

M, Jerlin Seles, and Dr U. Mary. "Strategy on Disaster Recovery Management based on Graph Theory Concepts." International Journal of Recent Technology and Engineering (IJRTE) 10, no. 4 (November 30, 2021): 31–34. http://dx.doi.org/10.35940/ijrte.d6535.1110421.

Повний текст джерела

Анотація:

The COVID-19 pandemic has asserted major baseline facts from disaster anthropology during the last three decades. Resilience could be based on the solution to the question: "What is the maximum amount of destruction, if any, that the graph (a network) can sustain while ensuring that at least one of each technology type remains and that the remaining induced subgraph is properly colored?" The concept of a graph's Chromatic Core Subgraph is a solution to the stated problem. In this paper, the pandemic graphs and certain sequential graphs are developed. For these graphs, the Chromatic core subgraph is obtained. The results of the pandemic graphs' Chromatic core subgraph are used to develop a disaster recovery strategy for the COVID-19 pandemic.

Стилі APA, Harvard, Vancouver, ISO та ін.

2

Axenovich, Maria, Tao Jiang, and Z. Tuza. "Local Anti-Ramsey Numbers of Graphs." Combinatorics, Probability and Computing 12, no. 5-6 (November 2003): 495–511. http://dx.doi.org/10.1017/s0963548303005868.

Повний текст джерела

Анотація:

A subgraph H in an edge-colouring is properly coloured if incident edges of H are assigned different colours, and H is rainbow if no two edges of H are assigned the same colour. We study properly coloured subgraphs and rainbow subgraphs forced in edge-colourings of complete graphs in which each vertex is incident to a large number of colours.

Стилі APA, Harvard, Vancouver, ISO та ін.

3

KOSTOCHKA, ALEXANDR, and MATTHEW YANCEY. "Large Rainbow Matchings in Edge-Coloured Graphs." Combinatorics, Probability and Computing 21, no. 1-2 (February 2, 2012): 255–63. http://dx.doi.org/10.1017/s0963548311000605.

Повний текст джерела

Анотація:

Arainbow subgraphof an edge-coloured graph is a subgraph whose edges have distinct colours. Thecolour degreeof a vertexvis the number of different colours on edges incident withv. Wang and Li conjectured that fork≥ 4, every edge-coloured graph with minimum colour degreekcontains a rainbow matching of size at least ⌈k/2⌉. A properly edge-colouredK4has no such matching, which motivates the restrictionk≥ 4, but Li and Xu proved the conjecture for all other properly coloured complete graphs. LeSaulnier, Stocker, Wenger and West showed that a rainbow matching of size ⌊k/2⌋ is guaranteed to exist, and they proved several sufficient conditions for a matching of size ⌈k/2⌉. We prove the conjecture in full.

Стилі APA, Harvard, Vancouver, ISO та ін.

4

Manoussakis, Y., M. Spyratos, Zs Tuza, and M. Voigt. "Minimal colorings for properly colored subgraphs." Graphs and Combinatorics 12, no. 4 (December 1996): 345–60. http://dx.doi.org/10.1007/bf01858468.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

5

Rödl, Vojtech, and Zsolt Tuza. "Rainbow subgraphs in properly edge-colored graphs." Random Structures & Algorithms 3, no. 2 (1992): 175–82. http://dx.doi.org/10.1002/rsa.3240030207.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

6

Katić, Robert, Colton Magnant, and Pouria Salehi Nowbandegani. "Forbidden Properly Edge-Colored Subgraphs that Force Large Highly Connected Monochromatic Subgraphs." Graphs and Combinatorics 33, no. 4 (May 26, 2017): 969–79. http://dx.doi.org/10.1007/s00373-017-1804-5.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

7

Alon, Noga, Tao Jiang, Zevi Miller, and Dan Pritikin. "Properly colored subgraphs and rainbow subgraphs in edge-colorings with local constraints." Random Structures and Algorithms 23, no. 4 (November 11, 2003): 409–33. http://dx.doi.org/10.1002/rsa.10102.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

8

Jaradat, M. M. M., M. S. A. Bataineh, and S. M. E. Radaideh. "Ramsey Numbers for Theta Graphs." International Journal of Combinatorics 2011 (June 15, 2011): 1–9. http://dx.doi.org/10.1155/2011/649687.

Повний текст джерела

Анотація:

The graph Ramsey number is the smallest integer with the property that any complete graph of at least vertices whose edges are colored with two colors (say, red and blue) contains either a subgraph isomorphic to all of whose edges are red or a subgraph isomorphic to all of whose edges are blue. In this paper, we consider the Ramsey numbers for theta graphs. We determine , for . More specifically, we establish that for . Furthermore, we determine for . In fact, we establish that if is even, if is odd.

Стилі APA, Harvard, Vancouver, ISO та ін.

9

Markström, Klas, Andrew Thomason, and Peter Wagner. "Properly Edge-Coloured Subgraphs in Colourings of Bounded Degree." Graphs and Combinatorics 27, no. 2 (September 1, 2010): 243–49. http://dx.doi.org/10.1007/s00373-010-0970-5.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

10

Magnant, Colton, Daniel M. Martin, and Pouria Salehi Nowbandegani. "Monochromatic Subgraphs in the Absence of a Properly Colored 4-Cycle." Graphs and Combinatorics 34, no. 6 (October 8, 2018): 1147–58. http://dx.doi.org/10.1007/s00373-018-1955-z.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

11

Alon, Noga, Alexey Pokrovskiy, and Benny Sudakov. "Random subgraphs of properly edge-coloured complete graphs and long rainbow cycles." Israel Journal of Mathematics 222, no. 1 (October 2017): 317–31. http://dx.doi.org/10.1007/s11856-017-1592-x.

Повний текст джерела

Стилі APA, Harvard, Vancouver, ISO та ін.

12

JOUVE, FLORENT, and JEAN-SÉBASTIEN SERENI. "EXPANDER GRAPHS AND SIEVING IN COMBINATORIAL STRUCTURES." Journal of the Australian Mathematical Society 105, no. 1 (January 11, 2018): 79–102. http://dx.doi.org/10.1017/s1446788717000234.

Повний текст джерела

Анотація:

We prove a general large-sieve statement in the context of random walks on subgraphs of a given graph. This can be seen as a generalization of previously known results where one performs a random walk on a group enjoying a strong spectral gap property. In such a context the point is to exhibit a strong uniform expansion property for a suitable family of Cayley graphs on quotients. In our combinatorial approach, this is replaced by a result of Alon–Roichman about expanding properties of random Cayley graphs. Applying the general setting we show, for instance, that with high probability (in a strong explicit sense) random coloured subsets of integers contain monochromatic (nonempty) subsets summing to $0$, and that a random colouring of the edges of a complete graph contains a monochromatic triangle.

Стилі APA, Harvard, Vancouver, ISO та ін.

13

Erzurumluoğlu, Aras, and C. A. Rodger. "On Evenly-Equitable, Balanced Edge-Colorings and Related Notions." International Journal of Combinatorics 2015 (March 4, 2015): 1–7. http://dx.doi.org/10.1155/2015/201427.

Повний текст джерела

Анотація:

A graph G is said to be even if all vertices of G have even degree. Given a k-edge-coloring of a graph G, for each color i∈Zk={0,1,…,k-1} let G(i) denote the spanning subgraph of G in which the edge-set contains precisely the edges colored i. A k-edge-coloring of G is said to be an even k-edge-coloring if for each color i∈Zk, G(i) is an even graph. A k-edge-coloring of G is said to be evenly-equitable if for each color i∈Zk, G(i) is an even graph, and for each vertex v∈V(G) and for any pair of colors i,j∈Zk, |degG(i)(v)-degG(j)(v)|∈{0,2}. For any pair of vertices {v,w} let mG({v,w}) be the number of edges between v and w in G (we allow v=w, where {v,v} denotes a loop incident with v). A k-edge-coloring of G is said to be balanced if for all pairs of colors i and j and all pairs of vertices v and w (possibly v=w), |mG(i)({v,w})-mG(j)({v,w})|≤1. Hilton proved that each even graph has an evenly-equitable k-edge-coloring for each k∈N. In this paper we extend this result by finding a characterization for graphs that have an evenly-equitable, balanced k-edge-coloring for each k∈N. Correspondingly we find a characterization for even graphs to have an evenly-equitable, balanced 2-edge-coloring. Then we give an instance of how evenly-equitable, balanced edge-colorings can be used to determine if a certain fairness property of factorizations of some regular graphs is satisfied. Finally we indicate how different fairness notions on edge-colorings interact with each other.

Стилі APA, Harvard, Vancouver, ISO та ін.

14

Yuster, Raphael. "Rainbow $H$-factors." Electronic Journal of Combinatorics 13, no. 1 (February 15, 2006). http://dx.doi.org/10.37236/1039.

Повний текст джерела

Анотація:

An $H$-factor of a graph $G$ is a spanning subgraph of $G$ whose connected components are isomorphic to $H$. Given a properly edge-colored graph $G$, a rainbow $H$-subgraph of $G$ is an $H$-subgraph of $G$ whose edges have distinct colors. A rainbow $H$-factor is an $H$-factor whose components are rainbow $H$-subgraphs. The following result is proved. If $H$ is any fixed graph with $h$ vertices then every properly edge-colored graph with $hn$ vertices and minimum degree $(1-1/\chi(H))hn+o(n)$ has a rainbow $H$-factor.

Стилі APA, Harvard, Vancouver, ISO та ін.

15

Coll, Vincent, Colton Magnant, and Kathleen Ryan. "Structure of Colored Complete Graphs Free of Proper Cycles." Electronic Journal of Combinatorics 19, no. 4 (December 6, 2012). http://dx.doi.org/10.37236/2304.

Повний текст джерела

Анотація:

For a fixed integer $m$, we consider edge colorings of complete graphs which contain no properly edge colored cycle $C_{m}$ as a subgraph. Within colorings free of these subgraphs, we establish global structure by bounding the number of colors that can induce a spanning and connected subgraph. In the case of smaller cycles, namely $C_4,C_5$, and $C_6$, we show that our bounds are sharp.

Стилі APA, Harvard, Vancouver, ISO та ін.

16

Alishahi, Meysam. "Colorful Subhypergraphs in Uniform Hypergraphs." Electronic Journal of Combinatorics 24, no. 1 (February 3, 2017). http://dx.doi.org/10.37236/6154.

Повний текст джерела

Анотація:

There are several topological results ensuring in any properly colored graph the existence of a colorful complete bipartite subgraph, whose order is bounded from below by some topological invariants of some topological spaces associated to the graph. Meunier [Colorful subhypergraphs in Kneser hypergraphs, The Electronic Journal of Combinatorics, 2014] presented the first colorful type result for uniform hypergraphs. In this paper, we give some new generalizations of the $\mathbb{Z}_p$-Tucker lemma and by use of them, we improve Meunier's result and some other colorful results by Simonyi, Tardif, and Zsbán [Colourful theorems and indices of homomorphism complexes, The Electronic Journal of Combinatorics, 2014] and by Simonyi and Tardos [Colorful subgraphs in Kneser-like graphs, European Journal of Combinatorics, 2007] to uniform hypergraphs. Also, we introduce some new lower bounds for the chromatic number and local chromatic number of uniform hypergraphs. A hierarchy between these lower bounds is presented as well.

Стилі APA, Harvard, Vancouver, ISO та ін.

17

Zhang, Xiaoyan, Zan-Bo Zhang, Hajo Broersma, and Xuelian Wen. "On the complexity of edge-colored subgraph partitioning problems in network optimization." Discrete Mathematics & Theoretical Computer Science Vol. 17 no. 3, Discrete Algorithms (July 1, 2016). http://dx.doi.org/10.46298/dmtcs.2159.

Повний текст джерела

Анотація:

International audience Network models allow one to deal with massive data sets using some standard concepts from graph theory. Understanding and investigating the structural properties of a certain data set is a crucial task in many practical applications of network optimization. Recently, labeled network optimization over colored graphs has been extensively studied. Given a (not necessarily properly) edge-colored graph $G=(V,E)$, a subgraph $H$ is said to be <i>monochromatic</i> if all its edges have the same color, and called <i>multicolored</i> if all its edges have distinct colors. The monochromatic clique and multicolored cycle partition problems have important applications in the problems of network optimization arising in information science and operations research. We investigate the computational complexity of the problems of determining the minimum number of monochromatic cliques or multicolored cycles that, respectively, partition $V(G)$. We show that the minimum monochromatic clique partition problem is APX-hard on monochromatic-diamond-free graphs, and APX-complete on monochromatic-diamond-free graphs in which the size of a maximum monochromatic clique is bounded by a constant. We also show that the minimum multicolored cycle partition problem is NP-complete, even if the input graph $G$ is triangle-free. Moreover, for the weighted version of the minimum monochromatic clique partition problem on monochromatic-diamond-free graphs, we derive an approximation algorithm with (tight) approximation guarantee ln $|V(G)|+1$.

Стилі APA, Harvard, Vancouver, ISO та ін.

18

Gourvès, Laurent, Adria Lyra, Carlos A. Martinhon, and Jérôme Monnot. "On paths, trails and closed trails in edge-colored graphs." Discrete Mathematics & Theoretical Computer Science Vol. 14 no. 2, Graph Theory (September 3, 2012). http://dx.doi.org/10.46298/dmtcs.586.

Повний текст джерела

Анотація:

Graph Theory International audience In this paper we deal from an algorithmic perspective with different questions regarding properly edge-colored (or PEC) paths, trails and closed trails. Given a c-edge-colored graph G(c), we show how to polynomially determine, if any, a PEC closed trail subgraph whose number of visits at each vertex is specified before hand. As a consequence, we solve a number of interesting related problems. For instance, given subset S of vertices in G(c), we show how to maximize in polynomial time the number of S-restricted vertex (resp., edge) disjoint PEC paths (resp., trails) in G(c) with endpoints in S. Further, if G(c) contains no PEC closed trails, we show that the problem of finding a PEC s-t trail visiting a given subset of vertices can be solved in polynomial time and prove that it becomes NP-complete if we are restricted to graphs with no PEC cycles. We also deal with graphs G(c) containing no (almost) PEC cycles or closed trails through s or t. We prove that finding 2 PEC s-t paths (resp., trails) with length at most L > 0 is NP-complete in the strong sense even for graphs with maximum degree equal to 3 and present an approximation algorithm for computing k vertex (resp., edge) disjoint PEC s-t paths (resp., trails) so that the maximum path (resp., trail) length is no more than k times the PEC path (resp., trail) length in an optimal solution. Further, we prove that finding 2 vertex disjoint s-t paths with exactly one PEC s-t path is NP-complete. This result is interesting since as proved in Abouelaoualim et. al.(2008), the determination of two or more vertex disjoint PEC s-t paths can be done in polynomial time. Finally, if G(c) is an arbitrary c-edge-colored graph with maximum vertex degree equal to four, we prove that finding two monochromatic vertex disjoint s-t paths with different colors is NP-complete. We also propose some related problems.

Стилі APA, Harvard, Vancouver, ISO та ін.

19

Gowers, Timothy, and Oliver Janzer. "Improved bounds for the Erdős-Rogers function." Advances in Combinatorics, February 28, 2020. http://dx.doi.org/10.19086/aic.12048.

Повний текст джерела

Анотація:

[Ramsey's Theorem](https://en.wikipedia.org/wiki/Ramsey%27s_theorem) is one of the most prominent results in graph theory. In its simplest form, it asserts that every sufficiently large two-edge-colored complete graph contains a large monochromatic complete subgraph. This theorem has been generalized to a plethora of statements asserting that every sufficiently large structure of a given kind contains a large "tame" substructure. The article concerns a closely related problem: for a structure with a given property, find a substructure possessing an even stronger property. For example, what is the largest $K_3$-free induced subgraph of an $n$-vertex $K_4$-free graph? The answer to this question is approximately $n^{1/2}$. The lower bound is easy. If a given graph has a vertex of degree at least $n^{1/2}$, then its neighbors induce a $K_3$-free subgraph with at least $n^{1/2}$ vertices. Otherwise, a greedy procedure yields an independent set of size almost $n^{1/2}$. The argument generalizes to $K_s$-free induced subgraphs of $K_{s+1}$-free graphs. Dudek, Retter and Rödl provided a construction showing that the exponent $1/2$ cannot be improved and asked whether the same is the case for $K_s$-free induced subgraphs of $K_{s+2}$-free graphs. The authors answer this question by providing a construction of $K_{s+2}$-free $n$-vertex graphs with no $K_s$-free induced subgraph with $n^{\alpha_s}$ vertices with $\alpha_s<1/2$ for every $s\ge 3$. Their arguments extend to the case of $K_t$-free graphs with no large $K_s$-free induced subgraph for $s+2\le t\le 2s-1$ and $s\ge 3$.

Стилі APA, Harvard, Vancouver, ISO та ін.

20

Guo, Zhiwei, Christoph Brause, Maximilian Geißer, and Ingo Schiermeyer. "Compatible Spanning Circuits and Forbidden Induced Subgraphs." Graphs and Combinatorics 40, no. 1 (January 19, 2024). http://dx.doi.org/10.1007/s00373-023-02735-8.

Повний текст джерела

Анотація:

AbstractA compatible spanning circuit in an edge-colored graph G (not necessarily properly) is defined as a closed trail containing all vertices of G in which any two consecutively traversed edges have distinct colors. The existence of extremal compatible spanning circuits (i.e., compatible Hamilton cycles and compatible Euler tours) has been studied extensively. Recently, sufficient conditions for the existence of compatible spanning circuits visiting each vertex at least a specified number of times in specific edge-colored graphs satisfying certain degree conditions have been established. In this paper, we continue the research on sufficient conditions for the existence of such compatible s-panning circuits. We consider edge-colored graphs containing no certain forbidden induced subgraphs. As applications, we also consider the existence of such compatible spanning circuits in edge-colored graphs G with κ(G) ≥ α(G), κ(G) ≥ α(G) − 1 and κ (G) ≥ α(G), respectively. In this context, κ(G), α(G) and κ (G) denote the connectivity, the independence number and the edge connectivity of a graph G, respectively.

Стилі APA, Harvard, Vancouver, ISO та ін.

21

Fang, Chunqiu, Ervin Győri, and Jimeng Xiao. "On the Maximal Colorings of Complete Graphs Without Some Small Properly Colored Subgraphs." Graphs and Combinatorics, June 15, 2021. http://dx.doi.org/10.1007/s00373-021-02351-4.

Повний текст джерела

Анотація:

AbstractLet $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) be the maximum number of colors in an edge-coloring of $$K_{n}$$ K n with no properly colored copy of G. For a family $${\mathcal {F}}$$ F of graphs, let $$\mathrm{ex}(n, {\mathcal {F}})$$ ex ( n , F ) be the maximum number of edges in a graph G on n vertices which does not contain any graphs in $${\mathcal {F}}$$ F as subgraphs. In this paper, we show that $$\mathrm{pr}(K_{n}, G)-\mathrm{ex}(n, \mathcal {G'})=o(n^{2}), $$ pr ( K n , G ) - ex ( n , G ′ ) = o ( n 2 ) , where $$\mathcal {G'}=\{G-M: M \text { is a matching of }G\}$$ G ′ = { G - M : M is a matching of G } . Furthermore, we determine the value of $$\mathrm{pr}(K_{n}, P_{l})$$ pr ( K n , P l ) for sufficiently large n and the exact value of $$\mathrm{pr}(K_{n}, G)$$ pr ( K n , G ) , where G is $$C_{5}, C_{6}$$ C 5 , C 6 and $$K_{4}^{-}$$ K 4 - , respectively. Also, we give an upper bound and a lower bound of $$\mathrm{pr}(K_{n}, K_{2,3})$$ pr ( K n , K 2 , 3 ) .

Стилі APA, Harvard, Vancouver, ISO та ін.

22

Barát, János, András Gyárfás, and Géza Tóth. "Monochromatic spanning trees and matchings in ordered complete graphs." Journal of Graph Theory, November 15, 2023. http://dx.doi.org/10.1002/jgt.23058.

Повний текст джерела

Анотація:

AbstractWe study two well‐known Ramsey‐type problems for (vertex‐)ordered complete graphs. Two independent edges in ordered graphs can be nested, crossing, or separated. Apart from two trivial cases, these relations define six types of subgraphs, depending on which one (or two) of these relations are forbidden. Our first target is to refine a remark by Erdős and Rado that every 2‐coloring of the edges of a complete graph contains a monochromatic spanning tree. We show that forbidding one relation we always have a monochromatic (nonnested, noncrossing, and nonseparated) spanning tree in a 2‐edge‐colored ordered complete graph. On the other hand, if two relations are forbidden, then it is possible that we have monochromatic (nested, separated, and crossing) subtrees of size only in a 2‐colored ordered complete graph on vertices. Some of these results relate to drawings of complete graphs. For instance, the existence of a monochromatic nonnested spanning tree in 2‐colorings of ordered complete graphs verifies a more general conjecture for twisted drawings. Our second subject is to refine the Ramsey number of matchings, that is, pairwise independent edges for ordered complete graphs. Cockayne and Lorimer proved that for given positive integers , is the smallest integer with the following property: every ‐coloring of the edges of a complete graph contains a monochromatic matching with edges. We conjecture that this result can be strengthened: ‐colored ordered complete graphs on vertices contain monochromatic nonnested and also nonseparated matchings with edges. We prove this conjecture for some special cases including the following. (i) Every ‐colored ordered complete graph on vertices contains a monochromatic nonnested matching of size two ( case). We prove it by showing that the chromatic number of the subgraph of the Kneser graph induced by the nonnested 2‐matchings in an ordered complete graph on vertices is ‐chromatic. (ii) Every 2‐colored ordered complete graph on vertices contains a monochromatic nonseparated matching of size ( case). This is the hypergraph analog of a result of Kaiser and Stehlík who proved that the Kneser graph induced by the nonseparated 2‐matchings in an ordered complete graph on vertices is ‐chromatic.For nested, separated, and crossing matchings the situation is different. The smallest ensuring a monochromatic matching of size in every ‐coloring is in the first two cases and one less in the third case.

Стилі APA, Harvard, Vancouver, ISO та ін.

23

Janssen, Jeannette, Rogers Mathew, and Deepak Rajendraprasad. "Partial List Colouring of Certain Graphs." Electronic Journal of Combinatorics 22, no. 3 (September 20, 2015). http://dx.doi.org/10.37236/4283.

Повний текст джерела

Анотація:

The partial list colouring conjecture due to Albertson, Grossman, and Haas (2000) states that for every $s$-choosable graph $G$ and every assignment of lists of size $t$, $1 \leq t \leq s$, to the vertices of $G$ there is an induced subgraph of $G$ on at least $\frac{t|V(G)|}{s}$ vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with chromatic number at least $\frac{|V(G)|-1}{2}$, chordless graphs, and series-parallel graphs.

Стилі APA, Harvard, Vancouver, ISO та ін.

24

Assadi, Sepehr, Pankaj Kumar, and Parth Mittal. "Brooks' Theorem in Graph Streams: A Single-Pass Semi-Streaming Algorithm for $\Delta$-Coloring." TheoretiCS Phase 2 (August 25, 2023). http://dx.doi.org/10.46298/theoretics.23.9.

Повний текст джерела

Анотація:

Every graph with maximum degree $\Delta$ can be colored with $(\Delta+1)$ colors using a simple greedy algorithm. Remarkably, recent work has shown that one can find such a coloring even in the semi-streaming model. But, in reality, one almost never needs $(\Delta+1)$ colors to properly color a graph. Indeed, the celebrated \Brooks' theorem states that every (connected) graph beside cliques and odd cycles can be colored with $\Delta$ colors. Can we find a $\Delta$-coloring in the semi-streaming model as well? We settle this key question in the affirmative by designing a randomized semi-streaming algorithm that given any graph, with high probability, either correctly declares that the graph is not $\Delta$-colorable or outputs a $\Delta$-coloring of the graph. The proof of this result starts with a detour. We first (provably) identify the extent to which the previous approaches for streaming coloring fail for $\Delta$-coloring: for instance, all these approaches can handle streams with repeated edges and they can run in $o(n^2)$ time -- we prove that neither of these tasks is possible for $\Delta$-coloring. These impossibility results however pinpoint exactly what is missing from prior approaches when it comes to $\Delta$-coloring. We then build on these insights to design a semi-streaming algorithm that uses $(i)$ a novel sparse-recovery approach based on sparse-dense decompositions to (partially) recover the "problematic" subgraphs of the input -- the ones that form the basis of our impossibility results -- and $(ii)$ a new coloring approach for these subgraphs that allows for recoloring of other vertices in a controlled way without relying on local explorations or finding "augmenting paths" that are generally impossible for semi-streaming algorithms. We believe both these techniques can be of independent interest.

Стилі APA, Harvard, Vancouver, ISO та ін.

25

Cranston, Daniel W., and Landon Rabern. "Beyond Degree Choosability." Electronic Journal of Combinatorics 24, no. 3 (August 11, 2017). http://dx.doi.org/10.37236/6179.

Повний текст джерела

Анотація:

Let $G$ be a connected graph with maximum degree $\Delta$. Brooks' theorem states that $G$ has a $\Delta$-coloring unless $G$ is a complete graph or an odd cycle. A graph $G$ is degree-choosable if $G$ can be properly colored from its lists whenever each vertex $v$ gets a list of $d(v)$ colors. In the context of list coloring, Brooks' theorem can be strengthened to the following. Every connected graph $G$ is degree-choosable unless each block of $G$ is a complete graph or an odd cycle; such a graph $G$ is a Gallai tree. This degree-choosability result was further strengthened to Alon—Tarsi orientations; these are orientations of $G$ in which the number of spanning Eulerian subgraphs with an even number of edges differs from the number with an odd number of edges. A graph $G$ is degree-AT if $G$ has an Alon—Tarsi orientation in which each vertex has indegree at least 1. Alon and Tarsi showed that if $G$ is degree-AT, then $G$ is also degree-choosable. Hladký, Král', and Schauz showed that a connected graph is degree-AT if and only if it is not a Gallai tree. In this paper, we consider pairs $(G,x)$ where $G$ is a connected graph and $x$ is some specified vertex in $V(G)$. We characterize pairs such that $G$ has no Alon—Tarsi orientation in which each vertex has indegree at least 1 and $x$ has indegree at least 2. When $G$ is 2-connected, the characterization is simple to state.

Стилі APA, Harvard, Vancouver, ISO та ін.

Ми пропонуємо знижки на всі преміум-плани для авторів, чиї праці увійшли до тематичних добірок літератури. Зв'яжіться з нами, щоб отримати унікальний промокод!