Search Results: 1 - 10 of 100 matches for " "
All listed articles are free for downloading (OA Articles)
Page 1 /100
Display every page Item
Heuristic Algorithm for Graph Coloring Based On Maximum Independent Set
Journal of Applied Computer Science & Mathematics , 2012,
Abstract: A number of heuristic algorithms have been developed for the graph coloring problem, but unfortunately, on any given instance, they may produce colorings that are very far from optimal. In this paper we investigated and introduce a three heuristics algorithm to color a graph based on a maximum independent set. The select a node with minimum and maximum degree consecutively (Min_Max) algorithm is implemented, tested and compared with select a node with minimum degree first (SNMD), select a node with maximum degree first (SNXD) in terms of CPU time and size of graph with different densities (0.1,0.2,…,0.9 ). The result indicated that the Min_Max algorithm and SNXD is better than SNMD based on the time of first maximum independent set, running time of CPU and the number of coloring nodes.
Complexity of Grundy coloring and its variants  [PDF]
Edouard Bonnet,Florent Foucaud,Eun Jung Kim,Florian Sikora
Computer Science , 2014,
Abstract: The Grundy number of a graph is the maximum number of colors used by the greedy coloring algorithm over all vertex orderings. In this paper, we study the computational complexity of GRUNDY COLORING, the problem of determining whether a given graph has Grundy number at least $k$. We also study the variants WEAK GRUNDY COLORING (where the coloring is not necessarily proper) and CONNECTED GRUNDY COLORING (where at each step of the greedy coloring algorithm, the subgraph induced by the colored vertices must be connected). We show that GRUNDY COLORING can be solved in time $O^*(2.443^n)$ and WEAK GRUNDY COLORING in time $O^*(2.716^n)$ on graphs of order $n$. While GRUNDY COLORING and WEAK GRUNDY COLORING are known to be solvable in time $O^*(2^{O(wk)})$ for graphs of treewidth $w$ (where $k$ is the number of colors), we prove that under the Exponential Time Hypothesis (ETH), they cannot be solved in time $O^*(2^{o(w\log w)})$. We also describe an $O^*(2^{2^{O(k)}})$ algorithm for WEAK GRUNDY COLORING, which is therefore $\fpt$ for the parameter $k$. Moreover, under the ETH, we prove that such a running time is essentially optimal (this lower bound also holds for GRUNDY COLORING). Although we do not know whether GRUNDY COLORING is in $\fpt$, we show that this is the case for graphs belonging to a number of standard graph classes including chordal graphs, claw-free graphs, and graphs excluding a fixed minor. We also describe a quasi-polynomial time algorithm for GRUNDY COLORING and WEAK GRUNDY COLORING on apex-minor graphs. In stark contrast with the two other problems, we show that CONNECTED GRUNDY COLORING is $\np$-complete already for $k=7$ colors.
Maximum Number of Minimum Dominating and Minimum Total Dominating Sets  [PDF]
Anant Godbole,Jessie Jamieson,William Jamieson
Mathematics , 2013,
Abstract: Given a connected graph with domination (or total domination) number \gamma>=2, we ask for the maximum number m_\gamma and m_{\gamma,T} of dominating and total dominating sets of size \gamma. An exact answer is provided for \gamma=2and lower bounds are given for \gamma>=3.
Distance-two coloring of sparse graphs  [PDF]
Zdenek Dvorak,Louis Esperet
Mathematics , 2013, DOI: 10.1016/j.ejc.2013.09.002
Abstract: Consider a graph $G = (V, E)$ and, for each vertex $v \in V$, a subset $\Sigma(v)$ of neighbors of $v$. A $\Sigma$-coloring is a coloring of the elements of $V$ so that vertices appearing together in some $\Sigma(v)$ receive pairwise distinct colors. An obvious lower bound for the minimum number of colors in such a coloring is the maximum size of a set $\Sigma(v)$, denoted by $\rho(\Sigma)$. In this paper we study graph classes $F$ for which there is a function $f$, such that for any graph $G \in F$ and any $\Sigma$, there is a $\Sigma$-coloring using at most $f(\rho(\Sigma))$ colors. It is proved that if such a function exists for a class $F$, then $f$ can be taken to be a linear function. It is also shown that such classes are precisely the classes having bounded star chromatic number. We also investigate the list version and the clique version of this problem, and relate the existence of functions bounding those parameters to the recently introduced concepts of classes of bounded expansion and nowhere-dense classes.
The a-graph coloring problem  [PDF]
James A. Tilley
Mathematics , 2015,
Abstract: We study a graph-coloring problem posed for near-triangulations of the plane with a face of size 4, which we refer to as a-graphs, and show that it is equivalent to the 4-color problem. As in the 4-color problem, a minimal counterexample in the case of the a-graph coloring problem derives from an internally 6-connected planar triangulation. However, in a significant departure from conventional analysis of the 4-color problem, we show that a minimal a-graph counterexample satisfies a highly restrictive coloring condition, one that can be expressed succinctly in terms of equivalence classes under Kempe exchanges. We define A* to be the family of a-graphs that possess both the coloring property and the minimum degree and connectivity characteristics of a minimal a-graph counterexample and argue that a member of A* is likely to be a small graph. In a systematic and complete search among all candidate a-graphs of order not greater than 20, we discover only a single member of A*, the smallest possible: the a-graph that results from deleting any edge in the icosahedron. This finding, together with other arguments presented in the article, indicates that the icosahedron plays a central, and possibly unique, role in the 4-color problem.
New Results on Generalized Graph Coloring  [cached]
Vladimir E. Alekseev,Alastair Farrugia,Vadim V. Lozin
Discrete Mathematics & Theoretical Computer Science , 2004,
Abstract: For graph classes 1,..., k, Generalized Graph Coloring is the problem of deciding whether the vertex set of a given graph G can be partitioned into subsets V 1,...,V k so that V j induces a graph in the class j (j=1,2,...,k). If 1 =...= k is the class of edgeless graphs, then this problem coincides with the standard vertex k-COLORABILITY, which is known to be NP-complete for any k≥ 3. Recently, this result has been generalized by showing that if all i 's are additive hereditary, then the generalized graph coloring is NP-hard, with the only exception of bipartite graphs. Clearly, a similar result follows when all the i 's are co-additive.
Acyclic edge coloring of graphs  [PDF]
Tao Wang,Yaqiong Zhang
Computer Science , 2013, DOI: 10.1016/j.dam.2013.12.001
Abstract: An {\em acyclic edge coloring} of a graph $G$ is a proper edge coloring such that the subgraph induced by any two color classes is a linear forest (an acyclic graph with maximum degree at most two). The {\em acyclic chromatic index} $\chiup_{a}'(G)$ of a graph $G$ is the least number of colors needed in an acyclic edge coloring of $G$. Fiam\v{c}\'{i}k (1978) conjectured that $\chiup_{a}'(G) \leq \Delta(G) + 2$, where $\Delta(G)$ is the maximum degree of $G$. This conjecture is well known as Acyclic Edge Coloring Conjecture (AECC). A graph $G$ with maximum degree at most $\kappa$ is {\em $\kappa$-deletion-minimal} if $\chiup_{a}'(G) > \kappa$ and $\chiup_{a}'(H) \leq \kappa$ for every proper subgraph $H$ of $G$. The purpose of this paper is to provide many structural lemmas on $\kappa$-deletion-minimal graphs. By using the structural lemmas, we firstly prove that AECC is true for the graphs with maximum average degree less than four (\autoref{NMAD4}). We secondly prove that AECC is true for the planar graphs without triangles adjacent to cycles of length at most four, with an additional condition that every $5$-cycle has at most three edges contained in triangles (\autoref{NoAdjacent}), from which we can conclude some known results as corollaries. We thirdly prove that every planar graph $G$ without intersecting triangles satisfies $\chiup_{a}'(G) \leq \Delta(G) + 3$ (\autoref{NoIntersect}). Finally, we consider one extreme case and prove it: if $G$ is a graph with $\Delta(G) \geq 3$ and all the $3^{+}$-vertices are independent, then $\chiup_{a}'(G) = \Delta(G)$. We hope the structural lemmas will shed some light on the acyclic edge coloring problems.
Between Treewidth and Clique-width  [PDF]
Sigve Hortemo S?ther,Jan Arne Telle
Computer Science , 2014,
Abstract: Many hard graph problems can be solved efficiently when restricted to graphs of bounded treewidth, and more generally to graphs of bounded clique-width. But there is a price to be paid for this generality, exemplified by the four problems MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set that are all FPT parameterized by treewidth but none of which can be FPT parameterized by clique-width unless FPT = W[1], as shown by Fomin et al [7, 8]. We therefore seek a structural graph parameter that shares some of the generality of clique-width without paying this price. Based on splits, branch decompositions and the work of Vatshelle [18] on Maximum Matching-width, we consider the graph parameter sm-width which lies between treewidth and clique-width. Some graph classes of unbounded treewidth, like distance-hereditary graphs, have bounded sm-width. We show that MaxCut, Graph Coloring, Hamiltonian Cycle and Edge Dominating Set are all FPT parameterized by sm-width.
Edge dominating graph of a graph  [cached]
B. Basavanagoud,Sunilkumar M. Hosamani
Tamkang Journal of Mathematics , 2012, DOI: 10.5556/j.tkjm.43.2012.603-608
Abstract: The edge dominating graph $E_{D}(G)$ of a graph $G=(V,E)$ is a graph with $V(E_{D}(G))=E(G)cup S(G)$, where $S(G)$ is the set of all minimal edge dominating sets of $G$ with two vertices $u,vin V(E_{D}(G))$ adjacent if $uin E$ and $v$ is a minimal edge dominating set of $G$ containing $u$. In this paper, we establish the bounds on order and size, diameter and vertex(edge)connectivity.
The $k$-Dominating Graph  [PDF]
Ruth Haas,Karen Seyffarth
Mathematics , 2012,
Abstract: Given a graph $G$, the $k$-dominating graph of $G$, $D_k(G)$, is defined to be the graph whose vertices correspond to the dominating sets of $G$ that have cardinality at most $k$. Two vertices in $D_k(G)$ are adjacent if and only if the corresponding dominating sets of $G$ differ by either adding or deleting a single vertex. The graph $D_k(G)$ aids in studying the reconfiguration problem for dominating sets. In particular, one dominating set can be reconfigured to another by a sequence of single vertex additions and deletions, such that the intermediate set of vertices at each step is a dominating set if and only if they are in the same connected component of $D_k(G)$. In this paper we give conditions that ensure $D_k(G)$ is connected.
Page 1 /100
Display every page Item

Copyright © 2008-2017 Open Access Library. All rights reserved.