Log in

Relevant bibliographies by topics / K-coloring problem

Contents

Journal articles
Dissertations / Theses
Book chapters
Conference papers

Academic literature on the topic 'K-coloring problem'

Author: Grafiati

Published: 4 June 2021

Last updated: 15 February 2022

Create a spot-on reference in APA, MLA, Chicago, Harvard, and other styles

Select a source type:

Consult the lists of relevant articles, books, theses, conference reports, and other scholarly sources on the topic 'K-coloring problem.'

Next to every source in the list of references, there is an 'Add to bibliography' button. Press on it, and we will generate automatically the bibliographic reference to the chosen work in the citation style you need: APA, MLA, Harvard, Chicago, Vancouver, etc.

You can also download the full text of the academic publication as pdf and read online its abstract whenever available in the metadata.

Journal articles on the topic "K-coloring problem"

1

Bekos, Michael A., Michael Kaufmann, Stephen G. Kobourov, Konstantinos Stavropoulos, and Sankar Veeramoni. "The maximum k -differential coloring problem." Journal of Discrete Algorithms 45 (July 2017): 35–53. http://dx.doi.org/10.1016/j.jda.2017.08.001.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Gurski, Frank, Dominique Komander, and Carolin Rehs. "Oriented Coloring on Recursively Defined Digraphs." Algorithms 12, no. 4 (2019): 87. http://dx.doi.org/10.3390/a12040087.

Full text

Abstract:

Coloring is one of the most famous problems in graph theory. The coloring problem on undirected graphs has been well studied, whereas there are very few results for coloring problems on directed graphs. An oriented k-coloring of an oriented graph G = ( V , A ) is a partition of the vertex set V into k independent sets such that all the arcs linking two of these subsets have the same direction. The oriented chromatic number of an oriented graph G is the smallest k such that G allows an oriented k-coloring. Deciding whether an acyclic digraph allows an oriented 4-coloring is NP-hard. It follows that finding the chromatic number of an oriented graph is an NP-hard problem, too. This motivates to consider the problem on oriented co-graphs. After giving several characterizations for this graph class, we show a linear time algorithm which computes an optimal oriented coloring for an oriented co-graph. We further prove how the oriented chromatic number can be computed for the disjoint union and order composition from the oriented chromatic number of the involved oriented co-graphs. It turns out that within oriented co-graphs the oriented chromatic number is equal to the length of a longest oriented path plus one. We also show that the graph isomorphism problem on oriented co-graphs can be solved in linear time.

APA, Harvard, Vancouver, ISO, and other styles

3

GANDHI, RAJIV, BRADFORD GREENING, SRIRAM PEMMARAJU, and RAJIV RAMAN. "SUB-COLORING AND HYPO-COLORING INTERVAL GRAPHS." Discrete Mathematics, Algorithms and Applications 02, no. 03 (2010): 331–45. http://dx.doi.org/10.1142/s1793830910000693.

Full text

Abstract:

In this paper, we study the sub-coloring and hypo-coloring problems on interval graphs. These problems have applications in job scheduling and distributed computing and can be used as "subroutines" for other combinatorial optimization problems. In the sub-coloring problem, given a graph G, we want to partition the vertices of G into minimum number of sub-color classes, where each sub-color class induces a union of disjoint cliques in G. In the hypo-coloring problem, given a graph G, and integral weights on vertices, we want to find a partition of the vertices of G into sub-color classes such that the sum of the weights of the heaviest cliques in each sub-color class is minimized. We present a "forbidden subgraph" characterization of graphs with sub-chromatic number k and use this to derive a 3-approximation algorithm for sub-coloring interval graphs. For the hypo-coloring problem on interval graphs, we first show that it is NP-complete, and then via reduction to the max-coloring problem, show how to obtain an O( log n)-approximation algorithm for it.

APA, Harvard, Vancouver, ISO, and other styles

4

Sarkar, Ushnish, and Avishek Adhikari. "On characterizing radio k-coloring problem by path covering problem." Discrete Mathematics 338, no. 4 (2015): 615–20. http://dx.doi.org/10.1016/j.disc.2014.11.014.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Hertz, Alain, Brigitte Jaumard, and Marcus Poggi de Aragão. "Local optima topology for the k-coloring problem." Discrete Applied Mathematics 49, no. 1-3 (1994): 257–80. http://dx.doi.org/10.1016/0166-218x(94)90212-7.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

ISOBE, SHUJI, XIAO ZHOU, and TAKAO NISHIZEKI. "A POLYNOMIAL-TIME ALGORITHM FOR FINDING TOTAL COLORINGS OF PARTIAL k-TREES." International Journal of Foundations of Computer Science 10, no. 02 (1999): 171–94. http://dx.doi.org/10.1142/s0129054199000137.

Full text

Abstract:

A total coloring of a graph G is a coloring of all elements of G, i.e. vertices and edges, in such a way that no two adjacent or incident elements receive the same color. Many combinatorial problems can be efficiently solved for partial k-trees, that is, graphs of treewidth bounded by a constant k. However, no polynomial-time algorithm has been known for the problem of finding a total coloring of a given partial k-tree with the minimum number of colors. This paper gives such a first polynomial-time algorithm.

APA, Harvard, Vancouver, ISO, and other styles

7

Galinier, Philippe, Alain Hertz, and Nicolas Zufferey. "An adaptive memory algorithm for the k-coloring problem." Discrete Applied Mathematics 156, no. 2 (2008): 267–79. http://dx.doi.org/10.1016/j.dam.2006.07.017.

Full text

APA, Harvard, Vancouver, ISO, and other styles

8

Bouziri, Hend, El-Ghazali Talbi, and Khaled Mellouli. "A Cooperative Search Method for the k-Coloring Problem." Journal of Mathematical Modelling and Algorithms 7, no. 2 (2008): 125–42. http://dx.doi.org/10.1007/s10852-008-9081-1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

9

Braga, Mónica, and Javier Marenco. "Facets based on cycles and cliques for the acyclic coloring polytope." RAIRO - Operations Research 54, no. 6 (2020): 1863–74. http://dx.doi.org/10.1051/ro/2019098.

Full text

Abstract:

A coloring of a graph is an assignment of colors to its vertices such that any two vertices receive distinct colors whenever they are adjacent. An acyclic coloring is a coloring such that no cycle receives exactly two colors, and the acyclic chromatic number χA(G) of a graph G is the minimum number of colors in any such coloring of G. Given a graph G and an integer k, determining whether χA(G) ≤ k or not is NP-complete even for k = 3. The acyclic coloring problem arises in the context of efficient computations of sparse and symmetric Hessian matrices via substitution methods. In a previous work we presented facet-inducing families of valid inequalities based on induced even cycles for the polytope associated to an integer programming formulation of the acyclic coloring problem. In this work we continue with this study by introducing new families of facet-inducing inequalities based on combinations of even cycles and cliques.

APA, Harvard, Vancouver, ISO, and other styles

10

Nagarathinam, R., N. Parvathi, and . "Grundy Number of Some Chordal Graphs." International Journal of Engineering & Technology 7, no. 4.10 (2018): 64. http://dx.doi.org/10.14419/ijet.v7i4.10.20708.

Full text

Abstract:

For a given graph G and integer k, the Coloring problem is that of testing whether G has a k-coloring, that is, whether there exists a vertex mapping c : V → {1, 2, . . .} such that c(u) 12â‰ "> c(v) for every edge uv ∈ E. For proper coloring, colors assigned must be minimum, but for Grundy coloring which should be maximum. In this instance, Grundy numbers of chordal graphs like Cartesian product of two path graphs, join of the path and complete graphs and the line graph of tadpole have been executed

APA, Harvard, Vancouver, ISO, and other styles

Dissertations / Theses on the topic "K-coloring problem"

1

Bekos, Michael A., Michael Kaufmann, Stephen G. Kobourov, Konstantinos Stavropoulos, and Sankar Veeramoni. "The maximum k-differential coloring problem." ELSEVIER SCIENCE BV, 2017. http://hdl.handle.net/10150/626126.

Full text

Abstract:

Given an n-vertex graph Gand two positive integers d, k is an element of N, the (d, kn)-differential coloring problem asks for a coloring of the vertices of G(if one exists) with distinct numbers from 1 to kn(treated as colors), such that the minimum difference between the two colors of any adjacent vertices is at least d. While it was known that the problem of determining whether a general graph is (2, n)-differential colorable is NP-complete, our main contribution is a complete characterization of bipartite, planar and outerplanar graphs that admit (2, n)-differential colorings. For practical reasons, we also consider color ranges larger than n, i.e., k > 1. We show that it is NP-complete to determine whether a graph admits a (3, 2n)-differential coloring. The same negative result holds for the (left perpendicular 2n/3 right pendicular, 2n)-differential coloring problem, even in the case where the input graph is planar.

APA, Harvard, Vancouver, ISO, and other styles

2

Hu, Jun. "Algorithms for irreducible infeasible subset detection in CSP - Application to frequency planning and graph k-coloring." Phd thesis, Université de Technologie de Belfort-Montbeliard, 2012. http://tel.archives-ouvertes.fr/tel-00823559.

Full text

Abstract:

The frequency assignment (FAP) consists in assigning the frequency on the radio links of a network which satisfiesthe electromagnetic interference among the links. Given the limited spectrum resources for each application, the fre-quency resources are often insufficient to deploy a wireless network without interference. In this case, the network isover-contrained and the problem is infeasible. Our objective is to identify an area with heavy interference.The work presented here concerns the detection for one of these areas with an algorithmic approach based onmodeling the problem by CSP. The problem of frequency assignment can be modeled as a constraint satisfactionproblem (CSP) which is represented by a triple: a set of variables (radio links), a set of constraints (electromagneticinterference) and a set of available frequencies.The interfered area in CSP can be considered a subset of irreducible feasible subset (IIS). An IIS is a infeasiblesubproblem with irreducible size, that is to say that all subsets of an IIS are feasible. The identification of an IIS ina CSP refers to two general interests. First, locating an IIS can easily prove the infeasibility of the problem. Becausethe size of IIS is assumed to be smaller compared to the entire problem, its infeasibility is relatively easier to prove.Second, we can locate the reason of infeasibility, in this case, the decision maker can provide the solutions to relax theconstraints inside IIS, which perhaps leads to a feasible solution to the problem.This work proposes algorithms to identify an IIS in the over-constrained CSP. These algorithms have tested on the well known benchmarks of the FAP and of the problem of graph k-coloring. The results show a significant improve-ment on instances of FAP compared to known methods.

APA, Harvard, Vancouver, ISO, and other styles

3

Schornstein, Nancy M. "Computing the chromatic number of t-(v, k, [lambda]) designs. /." Online version of thesis, 1989. http://hdl.handle.net/1850/10617.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Bulín, Jakub. "Algebraický přístup k CSP." Master's thesis, 2010. http://www.nusl.cz/ntk/nusl-298756.

Full text

Abstract:

For a finite relational structure A, the Constraint Satisfaction Problem with template A, or CSP(A), is the problem of deciding whether an input relational structure X admits a homomorphism to A. The CSP dichotomy conjecture of Feder and Vardi states that for any A, CSP(A) is either in P or NP-complete. In the first part we present the algebraic approach to CSP and summarize known results about CSP for digraphs, also known as the H-coloring problem. In the second part we study a class of oriented trees called special polyads. Using the algebraic approach we confirm the dichotomy conjecture for special polyads. We provide a finer description of the tractable cases and give a construction of a special polyad T such that CSP(T) is tractable, but T does not have width 1 and admits no near-unanimity polymorphisms.

APA, Harvard, Vancouver, ISO, and other styles

Book chapters on the topic "K-coloring problem"

1

Bekos, Michael A., Michael Kaufmann, Stephen Kobourov, and Sankar Veeramoni. "The Maximum k-Differential Coloring Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2015. http://dx.doi.org/10.1007/978-3-662-46078-8_10.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Porumbel, Daniel Cosmin, Jin-Kao Hao, and Pascale Kuntz. "A Study of Evaluation Functions for the Graph K-Coloring Problem." In Lecture Notes in Computer Science. Springer Berlin Heidelberg, 2008. http://dx.doi.org/10.1007/978-3-540-79305-2_11.

Full text

APA, Harvard, Vancouver, ISO, and other styles

3

Gu, Shenshen. "An Improved Transiently Chaotic Neural Network for Solving the K-Coloring Problem." In Advances in Neural Networks — ISNN 2005. Springer Berlin Heidelberg, 2005. http://dx.doi.org/10.1007/11427391_120.

Full text

APA, Harvard, Vancouver, ISO, and other styles

4

Sarkar, Ushnish, and Avishek Adhikari. "Hole: An Emerging Character in the Story of Radio k-Coloring Problem." In Mathematical and Statistical Applications in Life Sciences and Engineering. Springer Singapore, 2017. http://dx.doi.org/10.1007/978-981-10-5370-2_1.

Full text

APA, Harvard, Vancouver, ISO, and other styles

5

Mahajani, Shruti, Pratyush Sharma, and Vijay Malviya. "A Novel Approach of Vertex Coloring Algorithm to Solve the K-Colorability Problem." In Social Networking and Computational Intelligence. Springer Singapore, 2020. http://dx.doi.org/10.1007/978-981-15-2071-6_64.

Full text

APA, Harvard, Vancouver, ISO, and other styles

6

Takefuji, Yoshiyasu. "Four-Coloring and K-Colorability Problems." In Neural Network Parallel Computing. Springer US, 1992. http://dx.doi.org/10.1007/978-1-4615-3642-0_3.

Full text

APA, Harvard, Vancouver, ISO, and other styles

7

Bertossi, Alan A., M. Cristina Pinotti, and Phalguni Gupta. "Scalable Algorithms for Server Allocation in Infostations." In Handbook of Research on Scalable Computing Technologies. IGI Global, 2010. http://dx.doi.org/10.4018/978-1-60566-661-7.ch027.

Full text

Abstract:

The server allocation problem arises in isolated infostations, where mobile users going through the coverage area require immediate high-bit rate communications such as web surfing, file transferring, voice messaging, email and fax. Given a set of service requests, each characterized by a temporal interval and a category, an integer k, and an integer hc for each category c, the problem consists in assigning a server to each request in such a way that at most k mutually simultaneous requests are assigned to the same server at the same time, out of which at most hc are of category c, and the minimum number of servers is used. Since this problem is computationally intractable, a scalable 2-approximation online algorithm is exhibited. Generalizations of the problem are considered, which contain bin-packing, multiprocessor scheduling, and interval graph coloring as special cases, and admit scalable on-line algorithms providing constant approximations.

APA, Harvard, Vancouver, ISO, and other styles

8

Braunstein, Alfredo, and Marc Mézard. "Constraint Satisfaction by Survey Propagation." In Computational Complexity and Statistical Physics. Oxford University Press, 2005. http://dx.doi.org/10.1093/oso/9780195177374.003.0011.

Full text

Abstract:

Methods and analyses from statistical physics are of use not only in studying the performance of algorithms, but also in developing efficient algorithms. Here, we consider survey propagation (SP), a new approach for solving typical instances of random constraint satisfaction problems. SP has proven successful in solving random k-satisfiability (k -SAT) and random graph q-coloring (q-COL) in the “hard SAT” region of parameter space [79, 395, 397, 412], relatively close to the SAT/UNSAT phase transition discussed in the previous chapter. In this chapter we discuss the SP equations, and suggest a theoretical framework for the method [429] that applies to a wide class of discrete constraint satisfaction problems. We propose a way of deriving the equations that sheds light on the capabilities of the algorithm, and illustrates the differences with other well-known iterative probabilistic methods. Our approach takes into account the clustered structure of the solution space described in chapter 3, and involves adding an additional “joker” value that variables can be assigned. Within clusters, a variable can be frozen to some value, meaning that the variable always takes the same value for all solutions (satisfying assignments) within the cluster. Alternatively, it can be unfrozen, meaning that it fluctuates from solution to solution within the cluster. As we will discuss, the SP equations manage to describe the fluctuations by assigning joker values to unfrozen variables. The overall algorithmic strategy is iterative and decomposable in two elementary steps. The first step is to evaluate the marginal probabilities of frozen variables using the SP message-passing procedure. The second step, or decimation step, is to use this information to fix the values of some variables and simplify the problem. The notion of message passing will be illustrated throughout the chapter by comparing it with a simpler procedure known as belief propagation (mentioned in ch. 3 in the context of error correcting codes) in which no assumptions are made about the structure of the solution space. The chapter is organized as follows. In section 2 we provide the general formalism, defining constraint satisfaction problems as well as the key concepts of factor graphs and cavities, using the concrete examples of satisfiability and graph coloring.

APA, Harvard, Vancouver, ISO, and other styles

9

Amanathulla, Sk, and Madhumangal Pal. "L(h,k)-Labeling of Intersection Graphs." In Handbook of Research on Advanced Applications of Graph Theory in Modern Society. IGI Global, 2020. http://dx.doi.org/10.4018/978-1-5225-9380-5.ch007.

Full text

Abstract:

One important problem in graph theory is graph coloring or graph labeling. Labeling problem is a well-studied problem due to its wide applications, especially in frequency assignment in (mobile) communication system, coding theory, ray crystallography, radar, circuit design, etc. For two non-negative integers, labeling of a graph is a function from the node set to the set of non-negative integers such that if and if, where it represents the distance between the nodes. Intersection graph is a very important subclass of graph. Unit disc graph, chordal graph, interval graph, circular-arc graph, permutation graph, trapezoid graph, etc. are the important subclasses of intersection graphs. In this chapter, the authors discuss labeling for intersection graphs, specially for interval graphs, circular-arc graphs, permutation graphs, trapezoid graphs, etc., and have presented a lot of results for this problem.

APA, Harvard, Vancouver, ISO, and other styles

Conference papers on the topic "K-coloring problem"

1

Saha, Amit, Debasri Saha, and Amlan Chakrabarti. "Circuit Design for K-coloring Problem and its Implementation on Near-term Quantum Devices." In 2020 IEEE International Symposium on Smart Electronic Systems (iSES) (Formerly iNiS). IEEE, 2020. http://dx.doi.org/10.1109/ises50453.2020.00015.

Full text

APA, Harvard, Vancouver, ISO, and other styles

2

Sobral, Gabriel A. G., Marina Groshaus, and André L. P. Guedes. "Biclique edge-choosability in some classes of graphs∗." In II Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2017. http://dx.doi.org/10.5753/etc.2017.3203.

Full text

Abstract:

In this paper we study the problem of coloring the edges of a graph for any k-list assignment such that there is no maximal monochromatic biclique, in other words, the k-biclique edge-choosability problem. We prove that the K3free graphs that are not odd cycles are 2-star edge-choosable, chordal bipartite graphs are 2-biclique edge-choosable and we present a lower bound for the biclique choice index of power of cycles and power of paths. We also provide polynomial algorithms to compute a 2-biclique (star) edge-coloring for K3-free and chordal bipartite graphs for any given 2-list assignment to edges.

APA, Harvard, Vancouver, ISO, and other styles

3

Sambinelli, M., C. N. Lintzmayer, C. N. Da Silva, and O. Lee. "Vertex partition problems in digraphs ⇤." In III Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2018. http://dx.doi.org/10.5753/etc.2018.3174.

Full text

Abstract:

Let D be a digraph and k be a positive integer. Linial (1981) conjectured that the k-norm of a k-minimum path partition of a digraph D is at most max{PC2 C |C| : C is a partial k-coloring of D}. Berge (1982) conjectured that every k-minimum path partition contains a partial k-coloring orthogonal to it. It is well known that Berge's Conjecture implies Linial's Conjecture. In this work, we verify Berge's Conjecture, and consequently Linial's Conjecture, for locally in-semicomplete digraphs and k-minimum path partitions containing only two paths. Moreover, we verify a conjecture related to Berge's and Linial's Conjectures for locally in-semicomplete digraphs.

APA, Harvard, Vancouver, ISO, and other styles

4

Monteiro, Bruno, and Vinicius Dos Santos. "Equitable Partition of Graphs into Independent Sets and Cliques." In IV Encontro de Teoria da Computação. Sociedade Brasileira de Computação - SBC, 2019. http://dx.doi.org/10.5753/etc.2019.6392.

Full text

Abstract:

A graph is (k, l) if its vertex set can be partitioned into k independent sets and l cliques. Deciding if a graph is (k, l) can be seen as a generalization of coloring, since deciding is a graph belongs to (k, 0) corresponds to deciding if a graph is k-colorable. A coloring is equitable if the cardinalities of the color classes differ by at most 1. In this paper, we generalize both the (k, l) and the equitable coloring problems, by showing that deciding whether a given graph can be equitably partitioned into k independent sets and l cliques is solvable in polynomial time if max(k, l) 2, and NP complete otherwise.

APA, Harvard, Vancouver, ISO, and other styles

5

Gemelli, Nathaniel, Jeffrey Hudack, and Jae C. Oh. "Virtual Structure Reduction on Distributed K-Coloring Problems." In 2013 IEEE/WIC/ACM International Joint Conferences on Web Intelligence (WI) and Intelligent Agent Technologies (IAT). IEEE, 2013. http://dx.doi.org/10.1109/wi-iat.2013.89.

Full text

APA, Harvard, Vancouver, ISO, and other styles

We offer discounts on all premium plans for authors whose works are included in thematic literature selections. Contact us to get a unique promo code!